class Solution(object):
    def findDuplicate(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        max_num = len(nums)
        for i in range(len(nums)):
            if nums[i] < max_num:
                nums[nums[i]] += max_num
            elif nums[i] < 2 * max_num:
                nums[nums[i] - max_num] += max_num
            else:
                return i
        for i in range(len(nums)):
            if nums[i] > 2 * max_num:
                return i



class Solution(object):
    def findPeakElement(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """

        nums.append(float('-inf'))
        nums.insert(0, float('-inf'))
        l = 0
        r = len(nums)
        while l <= r:
            
            mid = (l+r) // 2
            if nums[mid] > nums[mid-1] and nums[mid] > nums[mid+1]:
                return mid-1
            if nums[mid] < nums[mid-1]:
                r = mid - 1
            elif nums[mid] < nums[mid+1]:
                l = mid + 1

